// hard

// 给定两个正序数组nums1，nums2，找出并返回这两个正序数组的中位数
// 算法的时间复杂度应该为O(log(m+n))

// 思路：二分查找
// k表示 (n1 + n2 + 1) / 2,如何在两个有序数组中找到前k小的元素位置
// 如何从nums1数组中取出m1个元素，使得nums1第m1个元素或者nums2第m2 = k - m1个元素视为中位线位置
// 步骤
// 1. left指向nums1的头部位置0，right指向nums1的尾部位置n1
// 2. 每次取中间位置m1，则m2 = k - m1， 判断nums1[m1]和nums2[m2 - 1]的关系


// nums1[m1] < nums2[m2-1], nums1的m1个元素zh都不可能是第k个元素，说明m1取的有点小了，应该将m1右移
// nums1[m1] >= nums2[m2-1],m1的取值可能有点大了，应该将m1左移
function findMedianSortedArrays(nums1, nums2) {
    let n1 = nums1.length
    let n2 = nums2.length
    if (n1 > n2) {
        return findMedianSortedArrays(nums2, nums1)
    }
    let k = Math.floor((n1 + n2 + 1) / 2)
    let left = 0
    let right = n1
    while (left < right) {
        // 在nums1中取前m1个元素
        let m1 = left + Math.floor((right - left) / 2)
        // 在nums2中取前m2个元素
        let m2 = k - m1
        if (nums1[m1] < nums2[m2 - 1]) {
            // 说明 nums1中元素不够多
            left = m1 + 1
        } else {
            right = m1
        }
    }
    let m1 = left
    let m2 = k - m1
    let c1 = Math.max(m1 <= 0 ? -Infinity : nums1[m1 - 1], m2 <= 0 ? -Infinity : nums2[m2 - 1])
    if ((n1 + n2) % 2 === 1) {
        return c1
    }
    let c2 = Math.min(m1 >= n1 ? Infinity : nums1[m1], m2 >= n2 ? Infinity : nums2[m2])
    return (c1 + c2) / 2
}

let arr1 = [1, 2, 3, 4]
let arr2 = [3, 4, 5, 6, 7]
console.log(findMedianSortedArrays(arr1, arr2));

function findMedianSortedArrays2(nums1, nums2) {
    let tempArr = nums1.concat(nums2)
    tempArr.sort((a, b) => a - b)
    let length = tempArr.length
    if (length % 2 === 0) {
        return (tempArr[length / 2 - 1] + tempArr[length / 2]) / 2
    } else {
        return tempArr[Math.floor(length / 2)]
    }
}